/*
 * @lc app=leetcode.cn id=127 lang=cpp
 *
 * [127] 单词接龙
 */

// @lc code=start
class Solution
{
public:
    struct WordNode
    {
        string word;
        int step;
    };

    int ladderLength(string beginWord, string endWord, vector<string> &wordList)
    {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        if (dict.find(endWord) == dict.end())
        {
            return 0;
        }
        queue<WordNode> q;
        q.push(WordNode{beginWord, 1});
        while (!q.empty())
        {
            WordNode curr = q.front();
            q.pop();
            if (curr.word == endWord)
            {
                return curr.step;
            }
            for (int i = 0; i < curr.word.size(); i++)
            {
                string temp = curr.word;
                for (int j = 'a'; j <= 'z'; j++)
                {
                    temp[i] = j;
                    if (dict.find(temp) != dict.end())
                    {
                        dict.erase(temp);
                        q.push(WordNode{temp, curr.step + 1});
                    }
                }
            }
        }
        return 0;
    }
};
// @lc code=end
